#ifndef _contest_gcd_h_
#define _contest_gcd_h_

#include<stdint.h>
#include<assert.h>

namespace contest
{
/**
 * Greatest common divisor
 * @param u: First number 
 * @param v: Second number 
 **/
uint64_t gcd(uint64_t u, uint64_t v)
{
    uint64_t tmp;
    while (u > 0)
    {
        if (u < v)
        {
            tmp = u;
            u = v;
            v = tmp;
        }
        u %= v;
    }
    return v;
}

void test_gcd()
{
    assert(gcd(1, 1) == 1);
    assert(gcd(1, 2) == 1);
    assert(gcd(1, 3) == 1);
    assert(gcd(2, 3) == 1);
    assert(gcd(2, 4) == 2);
    assert(gcd(6, 4) == 2);
    assert(gcd(5, 10) == 5);
    assert(gcd(10,10) ==10);
}
}

#endif
